class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if (arr[0] > k) {
            return k;
        }

        int l = 0, r = arr.size() - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int x = arr[mid];
            if (x - mid - 1 >= k) {
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }

        int p = arr[r] - r - 1;
        return k - p + arr[r];
    }
};